#include <iostream>

using namespace std;

/*
 *  定义双向链表的节点
 */
class  QNode{
    public:
        char data;
        QNode * pre;
        QNode * next;
        QNode(){
            pre = NULL;
            next = NULL;
        }
};

/*
 * 定义可变长双向链表循环队列
 *
 */
class Queue{
    private:
        QNode *front;  //队列头指针
        QNode *rear;   //队列尾指针
        QNode *initNode; //队列最大数指针

        int size;  //当前队列元素个数
        int initSize;  //初始化队列长度

    public:
        //初始化空队列
        Queue(int n){
            front = NULL;
            rear = NULL;

            initSize = n > 0 ? n :1;
            size = 0;
            int i =0;

            QNode *tmpNode;
            // --initNode->>rear---->>---->>front
            while(i<initSize){
                tmpNode = new QNode();
                tmpNode->data =0;
                if(rear == NULL && front == NULL){
                    initNode =front = rear = tmpNode;
                }
                tmpNode->next= initNode;  //将新的节点后继指向原队尾节点
                initNode->pre= tmpNode;   //将当原队尾结点的前继指向新的节点
                initNode= tmpNode;        //移动尾最大容量指针指向新建的节点
                initNode->pre = front;    //队尾最大容量指针的前继为队头
                front->next = initNode;   //队头节点后继指向队尾最大容量节点
                i++;
            }
           // cout << initNode->pre<<"-----"<<front<<"----"<<rear<<"\n";
           // initNode = rear;  //最大容量指针指向队尾 
        }

        //判断队列是否为空
        bool isEmpty(){
            return (front == rear && size==0);
        }

        //判断队列是否已满
        bool isFull(){
            return (initSize <= size);
        }

        //压入队列
        bool push(char e){
            if(isEmpty()){
                //如果是空队列
                front->data = e;
                size = 1;
            }else if(isFull()){
                //如果队列已满,创建新的节点
                QNode *tmpNode = new QNode();
                tmpNode->data = e;
                tmpNode->next = rear;
                rear->pre = tmpNode;
                rear = tmpNode;  //移动尾指针指向新的队尾节点 
                initSize++;     //最大容量数加1
                size++;         //队列元素+1
                initNode = rear;  //移动最大容量指针
                initNode->pre = front;
                front->next = initNode;
            }else{
                rear = rear->pre;  //往后移动尾指针
                rear->data = e;
                size++;
            }
        } 

        //弹出队列
        char pop(){
            char a ;
            if(isEmpty()){
                return 0;
            }else{
                a = front->data;
                front->data = 0;          //清空弹出的数据
                front = front->pre;
                initNode = initNode->pre;  //往队尾方向移动指针
                size--;
            }
            return a;
        }

       //输出队列元素
        int output(){
            int i = size;
            cout <<"队列长度为"<<size<<"："; 
            QNode *tmpNode;
            tmpNode = front;
            cout <<"front< ";
            while(i>0){
                cout << tmpNode->data <<" ";
                tmpNode = tmpNode->pre;
                i--;
            }
            cout << " <";
        }

        int getSize(){
            return size;
        }
};
